% !TeX spellcheck = fr-moderne
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Beamer Presentation
% LaTeX Template
% Version 1.0 (10/11/12)
%
% This template has been downloaded from:
% http://www.LaTeXTemplates.com
%
% License:
% CC BY-NC-SA 3.0 (http://creativecommons.org/licenses/by-nc-sa/3.0/)
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%----------------------------------------------------------------------------------------
%	PACKAGES AND THEMES
%----------------------------------------------------------------------------------------

\documentclass{beamer}

\mode<presentation> {
\usetheme{Madrid} % very very good
}
\usepackage{pgfplots}
\usepackage{graphicx} % Allows including images
\usepackage{booktabs} % Allows the use of \toprule, \midrule and \bottomrule in tables
\usepackage{pgf,pgfpages}
\usepackage{units}
\usepackage{listings}
\usepackage[utf8]{inputenc}
\setbeamertemplate{bibliography item}{[\theenumiv]}

\usepackage[variablett]{lmodern}
\lstset{ %
  backgroundcolor=\color{white},
  language=C++,
  basicstyle=\ttfamily\scriptsize,
  keywordstyle=\color{blue}\ttfamily,
  stringstyle=\color{red}\ttfamily,
  commentstyle=\color{darkgreen}\ttfamily,
  breaklines=true,
  columns=flexible,
  literate={_}{\textsmallunderscore}1,
  captionpos=b,
  commentstyle=\color{green},
  deletekeywords={...},
  extendedchars=true,
  frame=single,
  keepspaces=true,                 
  keywordstyle=\color{blue},
  morekeywords={*,function, foreach, procedure, put, pop, remove,...},
  numbers=left,
  numbersep=5pt,
  numberstyle=\tiny\color{black},
  rulecolor=\color{black},
  showstringspaces=false,
  stepnumber=1,
  title=\lstname,
  mathescape=true
}



%----------------------------------------------------------------------------------------
%	TITLE PAGE
%----------------------------------------------------------------------------------------

\title{Techniques de consistance d'ordre supérieur} % The short title appears at the bottom of every slide, the full title is only on the title page
%\titlegraphic{\includegraphics[width=1.5cm]{./images/UCL_logo.png}}

\author[KHONG Minh Thanh]{
Etudiant: KHONG Minh Thanh\\
Superviseur: Yves Deville
}

\vspace{3cm}

\institute[UCL]{
Institute of Information and Communication Technologies, Electronics and Applied Mathematics (ICTEAM) \\ Université catholique de Louvain

}
\begin{document}

\begin{frame}
\titlepage % Print the title page as the first slide
\end{frame}

\begin{frame}
\frametitle{Overview} % Table of contents slide, comment this block out to remove it
\tableofcontents % Throughout your presentation, if you choose to use \section{} and \subsection{} commands, these will automatically be printed on this slide as an overview of your presentation
\end{frame}

%------------------------------------------------
\section{Motivation}
%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
\begin{itemize}
\item Les problèmes combinatoires sont omniprésents dans les industries ainsi que dans les services, tels que la planification, le routage de véhicules, le réseaux,\dots
\item La programmation par contrainte permet de résoudre efficacement ces problèmes par les représenter comme un problème de satisfaction de contraintes (optimisation) (CSP).
\item Un CSP est définie par un ensemble de variables qui ont un domaine fini et un ensemble de contraintes que la solution doit satisfaire.
\item La résolution d'un CSP combine deux étapes : \textit{propagation} et \textit{recherche}.

\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
La recherche
\begin{itemize}
\item La recherche permet de trouver une solution par assigner les valeurs possibles aux variables.
%\item L'assignation partielle doit satisfaire les contraintes portantes sur les variables assignées. 
%\item Si aucune valeur n'est trouvée, la branche de recherche est échouée.
%\item L'espace de recherche est considérée comme un arbre de recherche.
\item La taille de l'espace de recherche est exponentielle. 
\end{itemize}
La propagation

\begin{itemize}
\item La propagation permet de réduire l'espace de recherche sans enlever la solution.
\item Les différents niveaux d'élagage peuvent être atteints par une propriété de consistance.
\item La consistance de domaine (DC) est la propriété la plus utilisé pour la propagation.
%\item La propagation détecte également les échecs, et termine les branches de l'arbre de recherche, économise l'exploration inutile de l'espace de recherche.
\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}{Motivation}
Exemple de la consistance de domaine (DC) :

\begin{itemize}
\item Etant donné un CSP : \\
 $D(x)= D(y)= \{1,2,3,4,5\}$ et $c(x,y)= x \leq y -2$. 
 \includegraphics[width=10cm]{./images/DC_ex.png}
\item Ce problème n'est pas DC parce que $(x,4), (x,5), (y,1), (y,2)$ ne satisfont pas $c(x,y)$ (n'ont pas de DC-support)
\item Appliquer la consistance DC pour ce CSP, on obtient : $D(x)=\{1,2,3\}$ et $D(y)= \{3,4,5\}$.
\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
\begin{itemize}
\item La puissance d’élagage DC n'est pas assez pour résoudre ces problèmes.
\item Il a besoin des techniques de consistance d'ordre supérieur pour les résoudre.
\end{itemize}

\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Motivation}
Etant donné un CSP : 
 
$D(x) = D(y) = D(z) = \{1, 2\}$ et $c_1 : x \neq y, c_2 : y \neq z, c_3 : x \neq z$

\begin{figure}[ht]
\centering
\includegraphics[width=3cm]{./images/DC_no_solution.jpeg}
\caption{Un exemple d'un CSP qui est DC mais il n'y a pas de solution.}
\end{figure}

\begin{itemize}
\item Le CSP est DC car chaque valeur peut satisfaire chaque contrainte, par exemple : pour  $(x, 1)$, on a $(y, 2)$ pour $c_1$ et $(z, 2)$ pour $c_3$. Mais ce CSP n'a pas de solution. 
\end{itemize}
Si on applique une consistance plus forte, telle situation peut être évitée.
\end{frame}


%------------------------------------------------
\section{Etat de l'art}
%------------------------------------------------
\begin{frame}
\frametitle{Etat de l'art}
Pour le CSP binaire (ses contraintes sont binaires)
\begin{itemize}
\item Restricted Path Consistency (RPC) \cite{Berlandier1995Improving}
% : il assure si une valeur a une seul moyen pour satisfaire la contrainte, alors elle peut étendre aux triangle contraintes.
\item Path Inverse Consistency (PIC) \cite{Freuder1996Neighborhood}
% : il assure que chaque valeur peut étendre aux triangle contraintes.
\item Max Restricted Path consistency (MaxRPC) \cite{Debruyne1997From}
% : il assure que chaque valeur a au moins un support qui peut étendre aux n'importe triangle contraintes.
%\item Neighborhood Inverse Consistency (NIC)
%% : il assure que chaque valeur dans le domaine d'une variable peut étendre aux tous les voisinages de cette contraintes.
%\item Singleton Domain Consistency (SDC)
%% : quand on assigne une valeur à une variable, après avoir appliqué un algorithme pour DC, si le résultat est échec, alors cette valeur est enlevée.
\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Etat de l'art}
Pour le CSP non-binaire
\begin{itemize}
\item Restricted Pairwise Consistency (RPWC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
\item relational Path Inverse Consistency  (rPIC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
\item Max Restricted Pairwise Consistency (maxRPWC) \cite{Stergiou2006Inverse} \cite{Bessiere2008Domain}
\end{itemize}
\end{frame}


%------------------------------------------------
\section{Résultats du mémoire de fin d’études}
%------------------------------------------------
%------------------------------------------------
\begin{frame}
\frametitle{Résultats du mémoire de fin d’études}
\begin{itemize}
\item Ingénieur en Informatique et Mathématiques appliquées
	à l'Institut Polytechnique de Hanoï, Vietnam
\item Master en Informatique à l’Institut de la Francophonie pour l’Informatique au Vietnam
	\begin{itemize}
	\item Master 1 : Etudes générales
	\item Master 2 : Etudes spécialisées
		\begin{itemize}
		\item 	Option : Systèmes Intelligents \& Multimédia - Inscrit en double diplômation avec l'Université de La Rochelle
		\end{itemize}
	\end{itemize}
\item Stage de fin d’études de 6 mois au département d’Ingénierie Informatique d’UCL.
	\begin{itemize}
	\item Sujet : "Beyond domain consistency"
	\end{itemize}

\end{itemize}
\end{frame}

%------------------------------------------------
\begin{frame}
\frametitle{Résultats du mémoire de fin d’études}
Nous avons : 
\begin{itemize}
\item Etudié les consistances d'ordre supérieur existantes.
\item Intégré les algorithmes pour ces consistances dans le framework AbsCon.
\item Experimenté ces algorithmes.
\end{itemize}
\end{frame}

%------------------------------------------------
\section{Objectif du projet}
%------------------------------------------------
\begin{frame}
\frametitle{Objectif du projet}
\begin{itemize}
\item Développer de nouvelles techniques de consistance d'ordre supérieur dans le but d'accélérer la résolution de problèmes combinatoires complexes.
\item Envisager la combinaison des techniques de consistances existantes et nouvelles.
\item Développer les différents algorithmes réalisant ces consistances, et les intégrer dans un solveur existant (AbsCon), et les expérimenter sur des problèmes complexes.
\end{itemize}

\end{frame}


%------------------------------------------------
\section{Plan de travail}
%------------------------------------------------
\begin{frame}
\frametitle{Plan de travail}
\begin{itemize}
\item WP1. Etat de l'art, analyse et étude les techniques existantes de consistance d'ordre supérieur.
\item WP2. Introduction et définition de nouvelles consistances d'ordre supérieur.
\item WP3. Combinaison de différentes consistances d'ordre supérieur.
\item WP4. Conception et mis en œuvre des abstractions de calcul nécessaires.
\item WP5. Implémentation des consistances d'ordre supérieur dans un solveur.
\item WP6. Expérimentation et d'analyse.
\item WP7. Rédaction et publication.
\end{itemize}
\end{frame}


%------------------------------------------------
\section{Environnement de recherche}
%------------------------------------------------
\begin{frame}
\frametitle{Environnement de recherche}
\begin{itemize}
\item  Institute for Information and Communication Technologies, Electronics and Applied
Mathematics (ICTEAM) est un institut de recherche de l'Université catholique de Louvain.
   \begin{itemize}
   \item ICTEAM possède 50 professeurs et plus de 200 chercheurs.
   \end{itemize}
\item Le groupe de recherche des contraintes "Be Cool" dirigé par le Professeur Yves Deville, un expert en programmation par contraintes et de techniques de consistance.
%\item Le groupe développe des travaux théoriques et de prototypage, afin de valider leurs résultats sur des problèmes réels.
\item La thèse sera co-supervisé par le Professeur Christophe Lecoutre, un expert international en programmation par contraintes, à Centre de Recherche en Informatique de Lens, Université d'Artois.
%\item Christophe Lecoutre est un expert international en programmation par contraintes, et plus particulièrement dans les techniques de consistance et d'algorithmes.
\end{itemize}


\end{frame}


%------------------------------------------------
\section{Conclusion}
%------------------------------------------------
\begin{frame}
\frametitle{Conclusion}
\begin{itemize}
\item La consistance d'ordre supérieur est prometteuse pour résoudre les problèmes combinatoires complexes.
\item Les premiers résultats de notre approche sont positif.
\item Les techniques de consistance d'ordre supérieur seront développées et mises en œuvre dans un solveur existant (AbsCon).
\item L'application à résoudre les problèmes industriels comme la planification, le routage de véhicules, le réseau.
\end{itemize}

\end{frame}


%------------------------------------------------
\begin{frame}
\frametitle{References}
\footnotesize{
\begin{thebibliography}{99} % Beamer does not support BibTeX so references must be inserted manually as below

\bibitem{Stergiou2006Inverse} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{Berlandier1995Improving} Berlandier, P. "Improving domain filtering using restricted path consistency." Artificial Intelligence for Applications, 1995. Proceedings., 11th Conference on. IEEE, 1995.

\bibitem{Freuder1996Neighborhood} Freuder, Eugene C., and Charles D. Elfe. "Neighborhood inverse consistency preprocessing." AAAI/IAAI, Vol. 1. 1996.

\bibitem{Debruyne1997From} Debruyne, Romuald, and Christian Bessiere. "From restricted path consistency to max-restricted path consistency." Principles and Practice of Constraint Programming-CP97. Springer Berlin Heidelberg, 1997. 312-326.

\bibitem{Stergiou2006Inverse} Stergiou, Kostas, and Toby Walsh. "Inverse Consistencies for Non-Binary Constraints." FRONTIERS IN ARTIFICIAL INTELLIGENCE AND APPLICATIONS 141 (2006): 153.

\bibitem{Bessiere2008Domain} Bessiere, Christian, Kostas Stergiou, and Toby Walsh. "Domain filtering consistencies for non-binary constraints." Artificial Intelligence 172.6 (2008): 800-822.
%\bibitem{Lecoutre2013Constraint} Lecoutre, Christophe. Constraint Networks: Targeting Simplicity for Techniques and Algorithms. John Wiley \& Sons, 2013.
\end{thebibliography}
}
\end{frame}

%%------------------------------------------------
%
\begin{frame}
\Huge{\centerline{Merci de votre attention !}}
\end{frame}

%----------------------------------------------------------------------------------------

\end{document} 